The present invention relates generally to decoding of encoded data symbols, and more particularly to a traceback operation in Maximum Likelihood Sequence Estimation (MLSE) decoders.
Various error detection and correction techniques are used to increase the reliability of a communication system. The techniques involve encoding of the data symbol sequence to be transmitted, and decoding of the received encoded data symbol sequence. Therefore, before transmitting data over a communication channel, the data symbols are encoded into code sequences. This encoding can be performed using coding techniques such as convolutional coding. A receiver receives the encoded code sequences along with some noise such as communication channel noise. The noisy encoded code sequences then are decoded using a Maximum Likelihood Sequence Estimation (MLSE) decoder. MLSE decoders correct random errors that occur due to the acquired noise in the encoded sequence of data symbols.
The MLSE decoder decodes a convolutionally encoded data symbol sequence using prior knowledge of the possible encoder state transitions from a given state to the next state. The prior knowledge is based on the dependence of a given data state on past data. The state transitions that are permitted can be represented with a trellis diagram. Each node in the trellis diagram denotes the state of a data symbol sequence at a point in time. The branches connecting the nodes denote a state transition.
An MLSE decoder typically includes a branch metric unit, a path metric unit also referred to as an add-compare-select (ACS) operation unit, and a traceback unit. The branch metric unit calculates branch metrics of the trellis stages of the trellis diagram corresponding to the encoder. Branch metrics are code distances between input code sequences, and code sequences predicted in respective branches of the trellis diagram. The path metric unit calculates accumulated values, referred to as path metrics, of the branch metrics and selects paths with the least path metrics as surviving paths.
The traceback unit comprises a traceback memory, and performs a traceback operation to obtain the decoded data symbols. The traceback operation traces the maximum likelihood path through the trellis of state transitions and reconstructs the most likely path through the trellis to extract the original data sequence that was input to the encoder. The traceback operation involves memory accesses for performing memory read and write operations. A memory write operation comprises writing decision bits extracted from surviving paths into the traceback memory. A memory read operation comprises reading the stored decision bits from the traceback memory.
The traceback operation in the MLSE decoders typically requires memory access at a rate of L*f/r reads/sec, where L is the traceback length; f, measured in Hz, is the rate at which coded symbols are supplied to the decoder; and 1/r is the code rate. To prevent the decoder from overflowing with data, f≧fCODE—SYMB, and fCODE—SYMB=fDATA/r, where fCODE—SYMB bits/sec is the coded symbol rate and fDATA bits/sec is the uncoded bit rate. Therefore, f/r≧fCODE—SYMB/r.
The traceback length L is typically of the order of 8*K, where K is the constraint length of the convolution encoder. Therefore, for typical applications, where the values of K range from 5 to 9, the frequency of memory reads for traceback operations ranges from 40 to 72 times the rate at which coded symbols are supplied to the decoder. In systems where the data rate is high or the value of f is large, the number of memory reads and the traceback operation speed increases by a large magnitude. This leads to unacceptably high power.
Various conventional MLSE decoders decode one symbol at a time during the traceback operation. The traceback memory length of such decoders is of the order of 6-7K. Since, such decoders decode only one symbol at a time, the number of memory accesses required to decode all of the encoded data symbols is large. Therefore, the clock rate requirement as well as the power consumption of such decoders is high.
Other known MLSE decoders perform full-frame traceback, i.e., the traceback operation is performed on an entire frame of input encoded data sequence, once the entire frame is received. In such decoders, the traceback memory size is kept equal to the maximum frame size. In addition, due to the reception of frames smaller than the maximum size, large amounts of traceback memory are unused. Thus, on the one hand there is a large memory requirement and on the other hand there is underutilisation of memory in such MLSE decoders.
Therefore, there is a need for MLSE decoders with reduced numbers of memory accesses during a traceback operation, which reduces the clock speed requirement and the power consumption of the decoder.